#pragma once
#include<iostream>
#include<list>
#include <stack>
#include <queue>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include "STRNode.h"
#include "SocialGraph.h"
using namespace std;

struct STRTree {

	list<STRNode*> nodelist;
	list<STRNode*> rootnodes;
	STRNode* root;
	SocialGraph* social_graph;
	int totalnodenum = 0;

	STRTree(SocialGraph* social_graph, int topK) {
		this->social_graph = social_graph;

		clock_t tbegin = clock(), tend;
		getNodeList(topK);
		tend = clock();

		clock_t tbegin1 = clock(), tend1;
		rootnodes = createTree();
		tend1 = clock();
		cout << "createSTRTree time :  " << to_string(tend1 - tbegin1) << "ms" << endl;
		root = mergeRoot(rootnodes);

	}

	void getNodeList(int topK) {
		clock_t tbegin = clock(), tend;
		social_graph->readCommunity(topK);
		tend = clock();
		cout << "readCommunity need time :  " << to_string(tend - tbegin) << "ms" << endl;

		for (auto iter : social_graph->community) {
			list<STRNode*> child;
			nodelist.push_back(new STRNode(iter.second, true, child));
		}

	}


	struct cmpx {
		bool operator()(const STRNode* r1, const STRNode* r2) {
			if (r1->MBR->getCenter()->x <= r2->MBR->getCenter()->x) {
				return false;
			}
			else if (r1->MBR->getCenter()->x > r2->MBR->getCenter()->x) {
				return true;
			}
		}
	};

	struct cmpy {
		bool operator()(const STRNode* r1, const STRNode* r2) {
			if (r1->MBR->getCenter()->y <= r2->MBR->getCenter()->y) {
				return false;
			}
			else if (r1->MBR->getCenter()->y > r2->MBR->getCenter()->y) {
				return true;
			}
		}
	};

	list<STRNode*> createTree() {
		int nodec = 3;
		list<STRNode*> current = nodelist;
		totalnodenum += current.size();
		do {
			list<STRNode*> cur;
			int leafnodecount = (int)ceil(current.size() / nodec);
			int xsliceCapacity = (int)ceil(sqrt(leafnodecount));
			list<list<STRNode*>> slices = stripPartition(current, xsliceCapacity * nodec, true);

			for (auto slice : slices) {
				list<STRNode*> temp = slice;
				list<list<STRNode*>> yslices = stripPartition(temp, nodec, false);

				for (auto yslice : yslices) {
					STRNode* strnode = new STRNode(getMBR(yslice), false, yslice);
					cur.push_back(strnode);
				}

				current = cur;
				totalnodenum += current.size();
			}
		} while (current.size() > nodec);
		return current;
	}

	STRNode* mergeRoot(list<STRNode*> rootnodes) {
		STRNode* root;
		Rectangle* rect = getMBR(rootnodes);
		cout << "root :  " << fixed << setprecision(2) << rect->low->x << "  " << rect->low->y << "   " << rect->high->x << "   " << rect->high->y << endl;
		root = new STRNode(rect, false, rootnodes);
		return root;
	}

	Rectangle* getMBR(list<STRNode*> rootnodes) {
		float xmin = DBL_MAX;
		float ymin = DBL_MAX;
		float xmax = -DBL_MAX;
		float ymax = -DBL_MAX;
		for (auto node : rootnodes) {
			if (node->MBR->low->x < xmin)
				xmin = node->MBR->low->x;
			if (node->MBR->high->x > xmax)
				xmax = node->MBR->high->x;
			if (node->MBR->low->y < ymin)
				ymin = node->MBR->low->y;
			if (node->MBR->high->y > ymax)
				ymax = node->MBR->high->y;
		}
		return new Rectangle(xmin, ymin, xmax, ymax);
	}

	list<list<STRNode*>> stripPartition(list<STRNode*> plist, int sliceCapacity, bool flag) {
		int datasize = plist.size();
		int sliceCount = ceil(datasize / (sliceCapacity * 1.0));

		if (flag == true) {
			plist.sort(cmpx());
		}
		else {
			plist.sort(cmpy());
		}

		list<list<STRNode*>> slices;
		list<STRNode*>::iterator iter = plist.begin();
		for (int i = 0; i < sliceCount; i++) {
			int boundablesAddedToSlice = 0;
			list<STRNode*> temp;
			while (iter != plist.end()) {
				if (boundablesAddedToSlice >= sliceCapacity) break;
				STRNode* t = *iter;
				temp.push_back(t);
				boundablesAddedToSlice++;
				iter++;
			}
			slices.push_back(temp);
		}
		return slices;
	}

	void dfsTraverse() {
		stack<STRNode*> st;
		st.push(root);
		while (!st.empty()) {
			STRNode* node = st.top();
			st.pop();
			if (node->isLeaf) {
				node->MBR->toString();
			}
			else {
				node->MBR->toString();
				for (auto ch : node->child) {
					if (ch->isLeaf == true)
						cout << ch->com->label << "  ";
					st.push(ch);
				}
				cout << endl;
			}
		}
	}

	void bfsTraverse() {
		queue<STRNode*> que;
		que.push(root);
		int count = 1;
		while (!que.empty()) {
			int len = que.size();
			for (int i = 0; i < len; i++) {
				STRNode* node = que.front();
				que.pop();
				if (node->isLeaf == true) {
					node->MBR->toString();
				}
				else {
					node->MBR->toString();
					for (auto ch : node->child) {
						if (ch->isLeaf == true)
							cout << ch->com->label << "  ";
						que.push(ch);
					}
					cout << endl;
				}
			}
			count++;
		}
	}


};